class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        int hash[26]{0};
        for (auto& ch : magazine)
            ++hash[ch - 'a'];

        for (auto& ch : ransomNote)
        {
            if (--hash[ch - 'a'] < 0)
                return false;
        }

        return true;
    }
};


class Solution {
public:
    bool isIsomorphic(string s, string t) {
        int len = s.size();
        unordered_map<char, char> hash;
        bool used[256]{false};
        for (int i = 0; i < len; ++i)
        {
            if (!hash.count(s[i]))
            {
                if (used[t[i]])
                    return false;

                hash.insert({s[i], t[i]});
                used[t[i]] = true;
            }
            else
            {
                if (hash[s[i]] != t[i])
                    return false;
            }
        }

        return true;
    }
};

class Solution {
public:
    bool wordPattern(string pattern, string s) {
        unordered_map<char, string> hash;
        unordered_set<string> used; //记录s中的单词是否已经被使用过
        size_t index = 0;
        for (int i = 0; i < pattern.size(); ++i)
        {
            size_t pos = s.find(' ', index);
            string temp = s.substr(index, pos - index);
            index = pos + 1;

            if (!hash.count(pattern[i]))
            {
                if (used.count(temp))
                    return false;

                hash.insert({pattern[i], temp});
                used.insert(temp);
            }
            else
            {
                if (hash[pattern[i]] != temp)
                    return false;
            }
        }

        return index == 0;  //如果最终index-0，说明已经遍历完s中的所有单词
    }
};

class Solution {
public:
    bool isAnagram(string s, string t) {
        int hash[26]{0};
        int n = s.size();

        for (auto& ch : s)
            ++hash[ch - 'a'];

        for (auto& ch : t)
        {
            --n;
           if (--hash[ch - 'a'] < 0)
                return false; 
        }
            

        return n == 0;
    }
};

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> ans;
        unordered_map<string, vector<string>> hash;

        auto tmp = strs;
        for (int i = 0; i < tmp.size(); ++i)
        {
            sort(tmp[i].begin(), tmp[i].end());
            hash[tmp[i]].push_back(strs[i]);
        }

        for (auto i : hash)
            ans.push_back(i.second);

        return ans;
    }
};	

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> ans(2, -1);
        unordered_map<int, int> hash;
        for (int i = 0; i < nums.size(); ++i)
        {
            if (hash.count(target - nums[i]))
            {
                ans[0] = i;
                ans[1]=  hash[target - nums[i]];
                break;
            }

            hash[nums[i]] = i;
        }

        return ans;
    }
};

class Solution {
private:
    int Sum(int n)
    {
        int sum = 0;
        while (n)
        {
            int tmp = n % 10;
            n /= 10;
            sum += tmp * tmp;
        }

        return sum;
    }
public:
    bool isHappy(int n) {
        int slow = n, fast = n;
        while (true)
        {
            slow = Sum(slow);
            fast = Sum(fast);
            fast = Sum(fast);

            if (slow == 1 || fast == 1)
                return true;
            else if (slow == fast)
                return false;
        }

        return false;
    }
};

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_map<int, int> hash;

        for (int i = 0; i < nums.size(); ++i)
        {
            if (hash.count(nums[i]) && abs(i - hash[nums[i]]) <= k)
                return true;

            hash[nums[i]] = i;
        }

        return false;
    }
};

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        int ans = 0;
        unordered_set<int> hash;
        for (auto& num : nums)
            hash.insert(num);

        for (auto& num : hash)
        {
            if (hash.count(num - 1))
                continue;

            int count = 1, tmp = num;
            while (hash.count(++tmp))
                ++count;

            ans = max(ans, count);
        }

        return ans;
    }
};